﻿//115. 不同的子序列
//给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

class Solution {
public:
    int numDistinct(string s, string t)
    {
        //dp[i][j] s[i]中t[j]出现的个数
        //s[i]==t[j] 
        //是 dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
        //否 dp[i][j]=dp[i-1][j]
        int m = s.size() + 1;
        int n = t.size() + 1;
        vector<vector<int>> dp(m, vector<int>(n));
        for (int i = 0; i < m; i++)        //t为空
        {
            dp[i][0] = 1;
        }
        for (int i = 1; i < n; i++)        //s为空
        {
            dp[0][i] = 0;
        }
        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
            {
                if (s[i - 1] == t[j - 1])
                {
                    dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % (1000000007);
                }
                else
                {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
};